package LC;

/**
 * https://leetcode.com/problems/unique-binary-search-trees/description/
 * Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
 * For example,
 * Given n = 3, there are a total of 5 unique BST's.
 */
public class LC_096_UniqueBinarySearchTrees_BinaryTree {
    public static void main(String[] args) {
        System.out.println(Solution.numTrees(3));
    }

    static class Solution {
        static int numTrees(int n) {
            if (n == 0 || n == 1) return 1;
            int res[] = new int[n + 1];
            res[0] = 1;
            for (int i = 1; i <= n; i++)
                for (int j = 0; j < i; j++)
                    res[i] += res[j] * res[i - j - 1];
            return res[n];
        }
    }
}
